#SortMoudle

#导入包
import math
count = 0


def GetArr_1():
    arr = [1,5,3,75,1,55,21,4,65,0,15,4]
    return arr

def GetArr_2():
    arr = [99,5,110,75,1,55,210,10,65,0,15,4]
    return arr

#特意为计数排序写造数据
def GetDataForCounttingSort():
    arr = [8,11,21,8,9,9,10,12,13,11,12,11,15,10,21]
    return arr


def ShowArr(arr):
    i = 0
    longth = len(arr)
    while(i < longth):
        print(arr[i],end=",")
        i = i + 1
    print("")


#冒泡排序
def BubbleSort(arr):
    longth = len(arr)   #计算数组的长度
    i = 0
    while(i < longth):
        j = 0
        while(j + 1 < longth - i):
            if arr[j] < arr[j + 1]:
                temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            j = j + 1
        i = i + 1

#选择排序
def SelectionSort(arr):
    sortedEnd = 0
    longth = len(arr)
    while(sortedEnd < longth):
        tempMaxPos = sortedEnd
        i = sortedEnd
        while(i < longth):
            if arr[i] > arr[tempMaxPos]:
                tempMaxPos = i
            i = i + 1
        temp = arr[sortedEnd]
        arr[sortedEnd] = arr[tempMaxPos]
        arr[tempMaxPos] = temp

        sortedEnd = sortedEnd + 1


#插入排序
def InsertionSort(arr):
    longth = len(arr)
    sortedEnd = 0
    ##i=sortedEnd+1
    #while(sortedEnd<longth-1):
    #    j = sortedEnd + 1;
    #    temp = arr[j]
    #    while(j>0):
    #        j = j-1
    #        if arr[j]>temp:
    #            arr[j+1] =temp
    #            break
    #        else:
    #            arr[j+1]=arr[j]
    #        if j==0:
    #            arr[0] = temp
    #    sortedEnd = sortedEnd+1


        
    while(sortedEnd < longth - 1):
        j = sortedEnd + 1
        temp = arr[j]
        while(j > 0):
            if arr[j - 1] > temp:
                break
            else:
                arr[j] = arr[j - 1]
            j = j - 1
        arr[j] = temp
        sortedEnd = sortedEnd + 1



#希尔排序
def ShellSort(arr):
    count = 0
    longth = len(arr)
    gap = math.floor(longth / 2)
    while(gap > 0):       #该循环用来缩小增量
        print(gap)
        i = 0           #缩小增量后，初始化i，从第0个小组开始排序
        while(i < gap):   #该循环用来遍历通过增量分的各个小组

            #对其中的每个小组使用插入排序
            #每个小组的首位是arr[i] 每次增量为gap
            #所以每个小组应该是 arr中的 [i,i+gap,i+2gap,i+3gap...]

            sortedEnd = i#sortedEnd用来标记该组已经排序过的成员的最后一位所在位置
            while(sortedEnd < longth - gap):#遍历该组，开始插入排序
                j = sortedEnd + gap     #遍历开始，获取尚未排序的下一个点的位置
                temp = arr[j]
                while(j > gap - 1):
                    count = count + 1
                    #print(j)
                    if (arr[j - gap] > temp):
                        break
                    else:
                        arr[j] = arr[j - gap]
                    j = j - gap
                arr[j] = temp

                sortedEnd = sortedEnd + gap
            
            i = i + 1
        
        gap = math.floor(gap / 2)#每次将间隔变为原来的一半

    print(count)

#希尔排序的另一种写法
def ShellSort_Other(arr):
    count = 0
    longth = len(arr)
    gap = math.floor(longth)
    while(gap > 0):       #该循环用来缩小增量

        i = 0           #缩小增量后，初始化i，从第0个小组开始排序
        while(i < longth - gap):   #该循环用来遍历通过增量分的各个小组
            pos = i + gap
            temp = arr[pos]
            while(pos > gap - 1):
                #此时并不是一次循环完某一个被分出来的小组
                #而是交叉着比较的，例如arr[0] a[gap]比完 a[1] a[gap+1]比
                #a[3] a[3+gap] ...直到a[gap]和a[2gap]比较
                #但是最终还是会各个小组比较完毕
                count = count + 1
                if arr[pos - gap] > temp:
                    break
                else:
                    arr[pos] = arr[pos - gap]
                pos = pos - gap
            arr[pos] = temp
            i = i + 1
        
        gap = math.floor(gap / 2)#每次将间隔变为原来的一半


    print(count)


#归并排序
def MergeSort(arr,start,end):
    print(start,end)
    if start == end:
        return arr[start]
    #if start == end - 1:
    #    if arr[start]>arr[end]:
    #        temp = arr[start]
    #        arr[start] = arr[end]
    #        arr[end] =temp
    mid = math.floor((end - start) / 2)

    left = MergeSort(arr,start,mid)
    right = MergeSort(arr,mid + 1,end)
    
    leftMax = len(left)
    rightMax = len(right)
    lcounter = 0
    rcounter = 0
    i = 0
    res = []
    while(i < len(left) + len(right) and lcounter < leftMax and rcounter < rightMax):
        if left[lcounter] > right[rcounter]:
            res.append(left[lcounter])
            lcounter = lcounter + 1
        else:
            res.append(right[rcounter])
            rcounter = rcounter + 1

    while(lcounter < leftMax):
        res.append(left[lcounter])
        lcounter = lcounter + 1

    while(rcounter < rightMax):
        res.append(right[rcounter])
        rcounter = rcounter + 1

    return res
#快速排序
def QuickSort(arr,start,end):
    if start >= end:
        return
    oldStart = start
    oldEnd = end

    while(start < end):
        while(start < end):
            if arr[end] < arr[start]:
                temp = arr[start]
                arr[start] = arr[end]
                arr[end] = temp
                start = start + 1
                break
            else:
                end = end - 1

        while(start < end):
            if arr[start] > arr[end]:
                temp = arr[start]
                arr[start] = arr[end]
                arr[end] = temp
                end = end - 1
                break
            else:
                start = start + 1

    QuickSort(arr,oldStart,start - 1)
    QuickSort(arr,end + 1,oldEnd)


#排序 其中的参数fun要使用者自己定义arr中的数据该如何比较,
#排序的时候使用快排
#示例1
#region 示例1
#def Compere(a,b):
#    if a[1]>b[1]:
#        return a
#    else:
#        return b

#arr = [[9,4],[1,1],[154,3],[55,5]]
#SortMoudle.SortUserDefFun(arr,Compere)
#print(arr)
#endregion 示例1

#示例2
#region 示例2
#准备数据
##region 准备数据
#class MyTestClassA:
#    lv = None
#    name = None
#a1 = MyTestClassA()
#a1.lv = 5
#a1.name = "a1"
#a2 = MyTestClassA()
#a2.lv = 1
#a2.name = "a2"
#a3 = MyTestClassA()
#a3.lv = 2
#a3.name = "a3"
#a4 = MyTestClassA()
#a4.lv = 100
#a4.name = "a4"
#arr = [a1,a2,a3,a4]
#print("Before Sort")
##endregion 准备数据
##定义比较用函数
#def Compere_CanBeAnyName(a,b):
#    if a.lv>b.lv:
#        return a
#    else:
#        return b

#i = 0
#while(i<len(arr)):
#    print(arr[i].name,arr[i].lv)
#    i = i+1
#SortMoudle.SortUserDefFun(arr,Compere_CanBeAnyName)
#print("After Sort")
#i = 0
#while(i<len(arr)):
#    print(arr[i].name,arr[i].lv)
#    i = i+1

#endregion 示例2

def SortUserDefFun(arr,fun):
    if fun == None:
        #print("Need define Second Prarm as Compare function")
        #print("function return the Biger Element")
        return false
    SortUserDefFunSupport(arr,0,len(arr)-1,fun)
    
    for a in arr:
        print(a.data,end = "")
    print("")

#本函数是给SortUserDefFun调用用的，这样SortUserDefFun函数就不用填写那么多参数了
def SortUserDefFunSupport(arr,start,end,fun):
    #print("Enter SortUserDefFunSupport")
    #print(start,end)
    if start >= end:
        return
    oldStart = start
    oldEnd = end

    while(start < end):
        while(start < end):
            #print(start,end)
            #if arr[start]==fun(arr[end],arr[start]):
            if arr[start]==fun(arr[start],arr[end]):
                temp = arr[start]
                arr[start] = arr[end]
                arr[end] = temp
                #start = start + 1
                break
            else:
                end = end - 1

        while(start < end):
            #if arr[start]==fun(arr[end],arr[start]):
            if arr[start]==fun(arr[start],arr[end]):
                temp = arr[start]
                arr[start] = arr[end]
                arr[end] = temp
                #end = end - 1
                break
            else:
                start = start + 1

    SortUserDefFunSupport(arr,oldStart,start - 1,fun)
    SortUserDefFunSupport(arr,end + 1,oldEnd,fun)
    pass

#堆排序
def HeapSort(arr):
    longth = len(arr)
    i=longth//2
    while(i>=0):
        AdjHeep(arr,i,longth-1)
        i=i-1

    end = longth-1
    while(end>0):
        print(arr)
        temp = arr[0]
        arr[0] = arr[end]
        arr[end] = temp
        end = end - 1
        AdjHeep(arr,0,end)
#堆排序中的调整堆
def AdjHeep(arr,root,end):
    maxTemp = root
    leftChild = root*2+1
    rightChild = leftChild + 1
    if leftChild>end:
        return;
    if arr[maxTemp]<arr[leftChild]:
        maxTemp = leftChild
    if rightChild<=end:
        if arr[maxTemp]<arr[rightChild]:
            maxTemp = rightChild
    if maxTemp == root:
        return
    else:
        valueTemp = arr[maxTemp]
        arr[maxTemp] = arr[root]
        arr[root] = valueTemp 
        AdjHeep(arr,maxTemp,end)


    #test
if __name__ == "__main__":
    #arr = GetArr_1()
    #arr = GetArr_2()
    arr = GetDataForCounttingSort()
    ShowArr(arr)
    #BubbleSort(arr)
    #SelectionSort(arr)
    #InsertionSort(arr)
    #ShellSort(arr)
    #ShellSort_Other(arr)
    #MergeSort(arr,0,len(arr))
    QuickSort(arr,0,len(arr) - 1)
    ShowArr(arr)
    #print(count)
    #print(math.floor(5/2))